【Leetcode】【python】Longest Valid Parentheses

题目大意

找出一个只包含”(“和”)”的字符串中最长的有效子字符串的长度。有效的意思是指该子字符串中的括号都能正确匹配。

解题思路

https://shenjie1993.gitbooks.io/leetcode-python/032%20Longest%20Valid%20Parentheses.html

采用了动态规划，dp[i]表示以i为子字符串末尾时的最大长度，最后的结果就是dp中的最大值。如果不是空字符串，则dp[0]=0，因为一个括号肯定无法正确匹配。递推关系是:

) ( ) ( ( ) ) )
0 0 2 0 0 2 6 0

代码

动态规划

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        length = len(s)
        dp = [0 for __ in range(length)]  # [0,0,0,0,0,0]
        
        for i in range(1, length):
            if s[i] == ")":
                j = i - 1 - dp[i - 1]  # 直接去查找前面的第n位，位移过了dp[i-1]位已经匹配的
                if j >= 0 and s[j] == "(":  # 如果那位是‘（’则可以总数多+2
                    dp[i] = dp[i - 1] + 2
                    if j - 1 >= 0:
                        dp[i] += dp[j - 1]  # 重点，会把这次匹配之前的加进去，例如（）（（））
        return max(dp)

栈

这题还可以用栈来解决，重点是栈内存储的是索引号，效率比动态规划好一些。

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        maxlen = 0
        stack = []
        last = -1
        for i in range(len(s)):
            if s[i]=='(':
                stack.append(i)     # push the INDEX into the stack!!!!
            else:
                if stack == []:
                    last = i
                else:
                    stack.pop()
                    if stack == []:
                        maxlen = max(maxlen, i-last)
                    else:
                        # print i, stack[len(stack)-1]
                        maxlen = max(maxlen, i-stack[len(stack)-1])
        return maxlen

总结